Unified messaging systems are positioned as centralized messaging solutions providing advantages in deployment cost, security and simplicity when compared to legacy voice mail systems implemented at each company location. One design goal for unified messaging systems may be to reduce the intelligence and complexity of the systems deployed in branch offices, while providing the same level of service to the users located in those offices. For example, a unified messaging system may implement a Voice Over Internet Protocol (VoIP) gateway at each branch office for an enterprise to provide VoIP services, such as establishing, managing and terminating packet-switched call sessions between multiple call terminals. The gateways may be arranged to communicate with a unified messaging server executed at a centralized data center over a data network, such as a Wide Area Network (WAN). The unified messaging server may provide certain messaging solutions for the branch office, such as recording and storing voice mail messages on behalf of call terminals typically serviced by the branch office when the call terminals are unavailable for a call session. Users of this centralized solution, however, may need assurances that some form of voice mail service will be maintained if the data network service connecting the branch office to the data center is interrupted. This is provided today by existing unified messaging systems by deploying more and more complex equipment at the branch offices, which may be inconsistent with the centralized model suitable for some unified messaging systems.